#include <stdio.h>
#include "Stack.h"
#include "QuickSort.h"

int QuickSort::Split(int list[], int left, int right)
{
	int i = left;
	int j = right+1;
	int pivot = list[i];
	do {
		do {
			++i;
		} while(list[i] < pivot);
		do {
			--j;
		} while(list[j] > pivot);
		if (i < j) {
			Swap(list[i], list[j]);	
		}
	} while(i < j);			
	Swap(list[left], list[j]);
	return j;
}

void QuickSort::Iterative(int list[], int n)
{
	Stack c;			
	
	int left = 0, right = n -1;	
	c.Push(left, right);
	while(c.size() > 0) {
		c.Top(left, right);
		c.pop();

		if (left < right) {
			int m = Split(list, left, right);
			c.Push(left, m-1);
			c.Push(m+1, right);
		}				
	}	
}

void QuickSort::Recursive(int list[], int left, int right)
{
	if (left < right) {
		int j = Split(list, left, right);
		Recursive(list, left, j-1);
		Recursive(list, j+1, right);	
	}
}

void QuickSort::Recursive(int list[], int n)
{
	Recursive(list, 0, n-1);
}
